The problem addressed by the present invention is how to "partition" a large set of product terms (sometimes referred to herein as logic terms) into subsets, herein called partitions. Each partition must not have more than a predetermined number of product/logic terms, so that it fits into a particular programmable logic array (PLA) device or into a "page" of a high density PLA. Furthermore, only one partition may be active or enabled at any one time. This means that the logic terms must be partitioned in such a way that only one partition or subset of logic terms needs to be evaluated during each clock cycle of the circuit.
Referring to FIGS. 1-4, in order to appreciate the problem addressed by the present invention, and its solution, we will first discuss the program logic array (PLA) circuitry typically used to implement large sets of logic terms, and the types of systems in which these PLA circuits are typically used.
Initially, programmable logic devices (PLDs) were used primarily for integrating multiple logic gate circuits into a single package, thereby reducing the number of parts used and the cost of manufacturing a particular circuit. Over time, high density PLDs were designed to integrate ever larger sets of logic functions onto a single chip. Effectively, one high density PLD takes the place of several lower density PLDs.
A well known problem associated with high density PLDs is their high power consumption. One solution to that problem introduced by National Semiconductor was to provide a family of PLD devices known as Multiple Array Programmable Logic (MAPL) devices, examples of which are the MAPL128 and MAPL144. The circuit data sheet for the MAPL128 and MAPL144 is published by National Semiconductor Corporation and is hereby incorporated by reference as background information. Also incorporated by reference is U.S. Pat. No. 4,942,319, which describes the internal operation of the MAPL devices.
Referring to FIG. 1, each MAPL device 100 contains multiple "pages" or partitions 102 of programmable logic circuits, each of which is functionally equivalent to a smaller PLD circuit. The MAPL device 100 also includes an array 110 of clocked registers 112 which generate binary output signals, a subset (S0-S2) of which are used as feedback signals by gates in the circuit pages.
The key feature of the MAPL device 100 is that only one page is enabled at one time. In particular, a subset of the register output signals determine which page 102 of the device 100 will be active during the next clock cycle of the device's master clock CLK. For instance, if the device 100 has eight pages 102, then three binary output signals will be used to determine which page is active. Since only one page 102 of the device is active at any one time, power consumption is reduced dramatically, thereby solving the problem associated with high density PLDs.
The operation of the MAPL device 100 is as follows. During each clock cycle, the currently enabled page "evaluates" specified logical combinations of the input signals and feedback signals, generating binary signals that are sent to the inputs of various ones of the registers 112. At the end of the clock cycle, the generated binary signals are latched into the registers. The outputs of the page selection registers S0-S2 determined which page 102 of the device will be enabled during the next clock cycle.
FIG. 2 shows a circuit 140, comprising eight interconnected programmable logic array (PLA) circuits 142, which is equivalent to the circuit in the MAPL device 100 shown in FIG. 1. Each PLA circuit 142 is enabled when the input to its output enable (OE) port is active. Furthermore, each PLA circuit has internal clocked registers (not shown) which generate its output signals. The outputs of the eight PLA circuits are wire-ORed together, which is possible because at any one time only one of the eight PLA circuits will be active. In any case, three of the output signals from the PLAs are used as feedback signals 143 that are decoded by eight AND gates 144, each with its output coupled to one of the PLA circuit's output enable ports, to determine which one of the eight PLA circuits will be active during each clock cycle.
The MAPL device 100 is particularly cost effective for implementing finite state machine circuits, including controllers, microinstruction sequences and other synchronous logic designs. FIG. 3 shows an example of a state diagram 160 for a finite state machine having eight states STO to ST7. The value on the vectors between states show the value of three binary signals required to change the state of the finite state machine from one state to another. To implement this state diagram with the circuitry of FIG. 1, each page 102 of the MAPL circuit is set up to evaluate the circuit's input signals while the state machine is in a corresponding state. Thus each page 102 corresponds to one of the states STx in FIG. 3. Similarly, using the circuit in FIG. 2, each state STx would correspond to one of the PLA circuits 142.
Referring to FIG. 4, there is shown a simplified representation of the circuitry in one of the PLA circuits 142 of FIG. 2. An example of a corresponding PLA specification for the product terms of this circuit is shown in Table 1.
TABLE 1 ______________________________________ .inputs: I1 I2 I3 F1 F2 F3 F4 .outputs: O1 O2 O3 O4 F1 F2 F3 F4 product terms: inputs outputs 1) 0001000 10001001 2) 0011000 10101011 3) 1-110-1 11111001 4) 1-01001 00001000 5) 0101010 01011000 . . . . . . . . . ______________________________________
This PLA specification lists three input signals (l1-l3), four output signals (O1-O4) and four feedback signals (F1-F4). Note that the feedback signals are included in both the input signal list and in the output signal list. Each product term in the PLA specification comprises a set of seven binary input values, three for the input signals and four for the feedback signals, and eight corresponding binary output values. A dash "-" represents a "don't care" value, meaning that it can be either a "1" or a "0".
Each AND gate 170 in FIG. 4 represents the input signal specification of one product term in the PLA specification. A first programmable connection matrix 172 connects input and feedback signals to each AND gate 170 in accordance with the input signal list of a corresponding product term in the PLA specification. In particular, on the input side of each PLA product, a "1" indicates that the corresponding input signal is to be connected to a corresponding AND gate. "0" and "-" values indicate that an input signal is not to be connected to the AND gate.
A second programmable connection matrix 174 connects the outputs of the AND gates to a set of OR gates 176 so as to match the values in the output portions of the specified product terms. On the output side of each PLA product term, a "1" indicates that the corresponding product term (i.e., the output of the corresponding AND gate) is to be connected to the OR gate for the corresponding output signal, while a "0" or "-" indicates no connection. The outputs from each OR gate 176 is latched in a corresponding register 178 at the end of each clock cycle.
An output enable signal OE is used to enable and disable the connection matrices 172 and 174 and the register circuits 178. When OE is not enabled, the circuit 142 dissipates very little power because no signals internal to the circuit are changing in value.
In the context of FIG. 1, each page 102 contains a connection matrix and a set of AND gates corresponding to the connection matrix 172 and AND gates 170 in FIG. 4. The array 110 of clocked registers 112 in FIG. 1 corresponds to the second connection matrix 174, OR gates 176 and registers 178 in FIG. 4.
Returning now to the problem addressed by the present invention, consider the situation in which a PLA specification contains more product terms than the number of AND gates in one page 102 of the MAPL circuit 100. Equivalently, in the context of the multiple PLA circuit shown in FIG. 2, the PLA specification contains more product terms than the number of AND gates in any one PLA circuit 142. The problem is to devise an automated system that partitions the product terms into subsets, herein called partitions, each no larger than one page 102, in such a way that only one partition needs to be enabled during each clock cycle.
For many circuits, such as finite state machines, the partitions are obvious to the circuit designer. In these situations the circuit designer will specify which feedback signals define the state of the circuit, eliminating the need for the present invention. However, there are many situations in which a design engineer will be asked to convert a specified synchronous logic circuit into a PLA circuit, without there being any immediately obvious method of dividing the resulting set of product terms into independent partitions. In fact, it is easy to devise circuits which are impossible to partition, simply because all product terms must be evaluated every clock cycle. On the other hand, many if not most sequential logic circuits tend can be partitioned, and the present invention provides an automated system and methodology for performing such partitioning.